<?php
/*
 * 你的王国里有n条龙，你希望雇佣一些勇士把它们杀死，王国里一共有m个骑士可以雇佣。
 * 假定，一个能力值 为x的骑士可以打败战斗力不超过x的恶龙，且需要支付x个金币。
 * 已知勇士可以重复雇佣，且重复雇佣需要重 复支付金币，请求出打败所有的恶龙需要的最小金币数目。
 * 例如，你的王国里有三条龙，战斗力分别为10，11，20，
 * 同时有三个勇士可以雇佣，能力值分别为 20,12,30，
 * 最省钱的方式是能力值12的勇士攻击战斗力10的龙，能力值12的勇士攻击战斗力11的龙，能力值 20的勇士攻击战斗力20的龙，总共付出44金币。
 *
 * 进阶：一条龙可以被勇士合力杀死，求付出的金币数
 *
 * 举例：
 * int[] knights = { 2, 10, 5 };
 * int[] dragons = { 3, 8, 6 };
 * 原问题标准下应返回：25
 * 进阶的标准下应返回：22
 */

// 题意就是：sum定死的前提下求最大的乘积
$knights = [2, 10, 5 ];
$dragons = [3, 8, 6 ];
$obj = new Code_02_WarriorGame();
$obj->main($knights, $dragons);

class Code_02_WarriorGame
{
    /*
     * 骑士排序，每个龙二分的去找刚好能烧死它的骑士
     * 如果骑士的数量N，龙的数量是M，时间复杂度就是O(MlogN)
     */
    public function main($knights, $dragons)
    {
        sort($knights);
        $res = 0;
        foreach ($dragons as $dragon) {
            $cost = $this->_getMinCost($knights, $dragon);
            if ($cost == PHP_INT_MAX) {
                echo 'max' . PHP_EOL;
                return PHP_INT_MAX;
            }
            $res += $cost;
        }
        echo $res . PHP_EOL;
        return $res;
    }

    protected function _getMinCost($knights, $dragon)
    {
        $L = 0;
        $R = count($knights) - 1;
        $key = -1;
        while ($L <= $R) {
            $mid = intval(($L + $R) / 2);
            if ($knights[$mid] < $dragon) {
                $L = $mid + 1;
            } else {
                $key = $mid;
                $R = $mid - 1;
            }
        }
        return $key == -1 ? PHP_INT_MAX : $knights[$key];
    }
}